#pragma once
#include<iostream>
using namespace std;

//BinarySearchTreeNode
namespace yjt
{
	template<class K>
	struct BSTreeNode
	{
		typedef BSTreeNode<K> Node;

		Node* _left;
		Node* _right;
		K _key;

		BSTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};
	//BinarySearchTree
	template<class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		bool Insert(const K& key)
		{
			if (!_root)
			{
				_root = new Node(key);
				return true;
			}
			Node* parent = nullptr;
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_key < key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;
			}

			cur = new Node(key);
			if (parent->_key > key)
				parent->_left = cur;
			else
				parent->_right = cur;

			return true;
		}
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_key > key)
					cur = cur->_left;
				else if (cur->_key < key)
					cur = cur->right;
				else
					return true;
			}
			return false;
		}

		void InOrder()
		{
			_InOrder(_root);
		}
		void _InOrder(Node* root)
		{
			if (root==nullptr) return;
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}
	private:
		Node* _root=nullptr;
	};


	void test()
	{
		BSTree<int> b1;
		int a[] = {8,3,1,10,6,4,7,14,13};
		for (auto x : a)
		{
			b1.Insert(x);
		}
		b1.InOrder();
	}

}